package com.wzq.solution;

class SolutionTmp {
    public int superpalindromesInRange(String L, String R) {
        
        Long l = Long.valueOf(L);
        Long r = Long.valueOf(R);
        long ls = (long)Math.sqrt(l);
        long rs = (long)Math.sqrt(r);
        int cnt=0;
        for(long i=ls;i<=rs;i++){
            if(isP(String.valueOf(i))){
                int len = String.valueOf(i).length();
                if(len%2 == 1){
                    cnt += oddLenStr(String.valueOf(i),rs);
                    long next = (long) Math.pow(10L,len)+1;

                    cnt += evenLenStr(String.valueOf(next),rs);



                }else{
                    cnt += evenLenStr(String.valueOf(i),rs);
                    long next = (long) Math.pow(10L,len)+1;
                    cnt += oddLenStr(String.valueOf(next),rs);

                }
                break;
            }
        }

        return cnt;

    }

    private static int oddLenStr(String str,Long r){
        int cnt = 0;
        String subStr = str.substring(0,str.length()/2+1);
        Long start = Long.valueOf(subStr);
        Long data = start;
        for(Long i = start;data <= r;i++){
            String s = String.valueOf(i);

            data = Long.valueOf(s + reverse(s.substring(0, s.length() - 1)));
            if(isP(String.valueOf(data*data))){
                cnt++;
            }
        }
        return cnt;
    }

    private static int evenLenStr(String str,Long r){
        int cnt = 0;
        String subStr = str.substring(0,str.length()/2);
        Long start = Long.valueOf(subStr);
        Long data = start;
        for(Long i = start;data <= r;i++){
            String s = String.valueOf(i);
            data = Long.valueOf(s + reverse(s));
            if(isP(String.valueOf(data*data))){
                cnt++;
            }
        }
        return cnt;
    }
    private  static String reverse(String str) {
        return new StringBuilder(str).reverse().toString();
    }
    
    private static boolean isP(String L){
        for(int i=0,j=L.length()-1;i<j;i++,j--){
            if(L.charAt(i) != L.charAt(j)){
                return false;
            }
        }
        return true;

    }

    public static void main(String[] args) {
        //superpalindromesInRange("1020762146323","142246798855636");
    }
}